import java.util.*;

public class Test {
    // 题目1：二叉树中第二小的节点
    // ans 设定为 第二小的数，找到了就退出
    // rootVal 就是整棵树根节点的值，也就是最小值了，找到一个比它严格大的数，这个数就是答案。
    int rootVal;
    int ans;
    public int findSecondMinimumValue(TreeNode root) {
        rootVal = root.val;
        ans = -1;
        dsf(root);
        return ans;
    }
    public void dsf1(TreeNode root){
        if(root == null){
            return;
        }
        if(ans != -1 && root.val >= rootVal){ // ♥♥♥♥♥♥♥♥这行出错啦！rootVal 改成 ans 才对！♥♥♥♥♥♥♥
            return;
        }
        if(root.val > rootVal){
            ans = root.val;
        }
        dsf1(root.left);
        dsf1(root.right);
    }

    // rootVal 是最小的，一开始时，找到任意一个比 rootVal严格大的，设为ans，但不能保证一定是第二小的。
    // 继续遍历去查找，比 ans 大的结点直接返回，而找到比 ans 严格小又比 rootVal 严格大的，ans 更新
    // 非常巧的一个题~
    public void dsf(TreeNode root){
        if(root == null){
            return;
        }
        if(ans != -1 && root.val >= ans){
            return;
        }
        if(root.val > rootVal){
            ans = root.val;
        }
        dsf(root.left);
        dsf(root.right);
    }

    // 题目2：恢复二叉搜索树
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode x , y, pre;
    public void recoverTree(TreeNode root) {
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(pre != null && root.val < pre.val){
                y = root;
                if(x == null){
                    x = pre;
                }else{
                    break;
                }
            }
            pre = root;
            root = root.right;
        }
        swap(x, y);
    }

    public void swap(TreeNode x, TreeNode y){
        int temp = x.val;
        x.val = y.val;
        y.val = temp;
    }

    int count;
    int ans1 = -1;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dsf2(root);
        return ans1;
    }
    public void dsf2(TreeNode root){
        if(root == null){
            return ;
        }
        dsf2(root.left);
        if(ans1 == -1 && count == 1){
            ans1 = root.val;
            return;
        }else{
            count--;
        }
        dsf2(root.right);
    }

    // 迭代写法：
    public int kthSmallest1(TreeNode root, int k) {
        Deque<TreeNode> stack = new LinkedList<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(k == 1){
                return root.val;
            }else{
                k--;
            }
            root = root.right;
        }
        return -1;
    }

    // 题目3：二叉搜索树中的众数
    //
    // 这个用递归会比迭代好，因为众数是必须遍历一遍二叉树的
    List<Integer> list = new LinkedList<>();
    int baseNum, count1, maxCount;
    public int[] findMode(TreeNode root) {
        mode(root);
        int size = list.size();
        int[] ret = new int[size];
        for(int i = 0; i < size; i++){
            ret[i] = list.get(i);
        }
        return ret;
    }
    public void mode(TreeNode root){
        if(root == null){
            return;
        }
        mode(root.left);
        fun(root.val);
        mode(root.right);
    }

    public void fun(int x){
        if(x == baseNum){
            count1++;
        }else{
            baseNum = x;
            count1 = 1;
        }
        if(count1 == maxCount){
            list.add(x);
        }
        if(count1 > maxCount){
            list.clear();
            list.add(x);
            maxCount = count1;
        }
    }
}




